package three;

import java.util.Scanner;

public class test10303 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] a = new int[n + 1][n + 1];
        int[][] m = new int[n + 1][n + 1];
//        s[][] 0来自正上方 -1来自左上方
        int[][] s = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                a[i][j] = scanner.nextInt();
            }
        }
        q(a, m, s, n);
        int max = a[1][1];
        for (int j = 1; j <= n; j++) {
            if (max <= m[n][j]) {
                max = m[n][j];
            }
        }
        System.out.println(max);
        Traceback(a, m, s, n);
    }

    private static void Traceback(int[][] a, int[][] m, int[][] s, int n) {
        int max = a[1][1];
        int k = 0;
        for (int j = 1; j <= n; j++) {
            if (max <= m[n][j]) {
                max = m[n][j];
                k = j;
            }
        }
        int[] b = new int[n + 1];
        b[n] = a[n][k];
        for (int i = n; i > 1; i--) {
            if (s[i][k] == 0) {
                b[i - 1] = a[i - 1][k];
            } else {
                k = k - 1;
                b[i - 1] = a[i - 1][k];
            }
        }
        for (int i = 1; i <= n; i++) {
            System.out.print(b[i] + " ");
        }
    }

    private static void q(int[][] a, int[][] m, int[][] s, int n) {
        m[1][1] = a[1][1];
        s[1][1] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (j == 1) {
                    m[i][j] = m[i - 1][j] + a[i][j];
                    s[i][j] = 0;
                } else if (j == i) {
                    m[i][j] = m[i - 1][j - 1] + a[i][j];
                    s[i][j] = -1;
                } else {
                    if (m[i - 1][j - 1] > m[i - 1][j]) {
                        m[i][j] = m[i - 1][j - 1] + a[i][j];
                        s[i][j] = -1;
                    } else {
                        m[i][j] = m[i - 1][j] + a[i][j];
                        s[i][j] = 0;
                    }
                }
            }
        }
    }
}
